package leetcode;

import java.util.ArrayList;
import java.util.List;

public class RestoreIPAddresses_Java {

    public List<String> restoreIpAddresses(String s) {

        ArrayList<String> result = new ArrayList<>();

        int len = s.length();
        if (len < 4 || len > 12)
            return result;
        for (int i = 1; i <= 3; i++) {

            //rest ip part  max len 3..9
            if (len - i > 9 || len - i < 3)
                continue;
            if (i > 1 && s.charAt(0) == '0')
                continue;
            if (i == 3 && s.charAt(0) >= '3')
                continue;

            for (int j = 1; j <= 3; j++) {

                if (len - i - j < 2 || len - i - j > 6)
                    continue;
                if (j > 1 && s.charAt(i) == '0')
                    continue;

                if (j == 3 && s.charAt(i) >= '3')
                    continue;

                for (int k = 1; k <= 3; k++) {
                    if (k > 1 && s.charAt(i + j) == '0')
                        continue;
                    if (k == 3 && s.charAt(i + j) >= '3')
                        continue;

                    int last = len - i - j - k;

                    if (last < 1 || last > 3)
                        continue;
                    if (last > 1 && s.charAt(i + j + k) == '0')
                        continue;
                    if (last == 3 && s.charAt(i + j + k) >= '3')
                        continue;

                    int part1 = Integer.parseInt(s.substring(0, i));
                    int part2 = Integer.parseInt(s.substring(i, i + j));
                    int part3 = Integer.parseInt(s.substring(i + j, i + j + k));
                    int part4 = Integer.parseInt(s.substring(i + j + k));

                    if (isValidIpPar(part1) && isValidIpPar(part2) && isValidIpPar(part3) && isValidIpPar(part4))
                        result.add(part1 + "." + part2 + "." + part3 + "." + part4);

                }
            }
        }

        return result;
    }


    public boolean isValidIpPar(int ipPart) {
        return ipPart > -1 && ipPart < 256;
    }

}
